package _0_4_买卖股票

/**
原题链接:
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/

309. 买卖股票的最佳时机含冷冻期
给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格.
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:
输入: prices = [1]
输出: 0

持有(买入) 持有 卖出 冷冻 不操作 买入 卖出
*/
// 最佳买卖股票时机含冷冻期 动态规划
// 时间复杂度O(n) 空间复杂度O(n)
func maxProfit309(prices []int) int {

	n := len(prices)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, 4)
	}

	dp[0][0] = -prices[0]
	for i := 1; i < n; i++ {
		dp[i][0] = max(dp[i-1][0], max(dp[i-1][1]-prices[i], dp[i-1][3]-prices[i])) //持有股票
		dp[i][1] = max(dp[i-1][1], dp[i-1][3])                                      //保持卖出股票
		dp[i][2] = dp[i-1][0] + prices[i]                                           //当天为具体卖出股票的日子
		dp[i][3] = dp[i-1][2]                                                       //当天为冷冻期, 那么前一天一定是具体卖出的日志
	}

	return max(dp[n-1][1], max(dp[n-1][2], dp[n-1][3]))
}
